All computers are required to process, and hence store, large amounts of information. Fast processing of information requires that the central processing unit of these computers be able to transfer that information at a high rate of speed. The storage medium used to store information will typically be the limiting factor of the transfer rates. Additional delays are caused by the time required by a storage device when a storage medium is initially loaded.
The fastest storage medium in a computer is main memory which is usually in the form of semiconductor random access memory (RAM). While main memory is very fast it is also volatile. Main memory use is thus limited to short term storage of currently active information. The remaining information storage requirements are typically handled by peripheral storage devices.
Peripheral storage devices include magnetic tape storage devices, Direct Access Storage Devices (DASD), and optical storage devices. Each of these storage devices has a substantially greater storage density and lower cost than main memory. However, the time to access information from each of these storage devices is also much greater than the access time of information from main memory. For example, main memory is accessed electronically and no mechanical movement is required. Peripheral storage devices, on the other hand, require that a particular area of tape or disk first be positioned under a read/write head before information accessing can begin.
While increasing amounts of data continue to be stored on a single storage medium, a corresponding problem occurs regarding defects. The number of defects per million of bits stored increases as the density of bits per unit area increase, in part, because a smaller area is required per bit, and hence smaller and smaller particles are capable of causing errors. As a result, storage media capable of storing large amounts of data, also have an increased number of defects. Dealing effectively with the increased number of defects generally requires more complex, and hence more expensive solutions. Access time to the data is a major concern and since many defects are handled in real time, the solution chosen to deal with the defects must be fast.
One defect management solution for storage media is error correction and detection. Parity generation and checking has been used to provide a means of determining whether data has been sent and received correctly (written and read back). In parity generation, when a string of bits is to be written, an extra bit is generated which is the exclusive-or of the bits to be written. This parity bit essentially is determining whether an even or odd number of binary ones are in the string of bits. The parity bit is then appended to the data. On read back, the parity bit is checked to determine if the string of bits still has an even or odd number of binary ones. Obviously if there is a two bit error, this parity scheme will fail to detect it. Additionally, parity generation does not identify which bit is in error.
Parity generation is fast and inexpensive and is useful for identifying single bit errors. Other methods are available for detecting errors of more than one bit, and additionally, for correcting those errors. Cyclic redundancy code (CRC) and error correction code (ECC) are examples of methods well known in the art for checking and correcting errors in data. Using CRC reduces the number of defects that need to be tracked and replaced on a storage medium. Some defects are too large, i.e., affect too many bits for CRC to be able to correct the errors. In these instances, it is necessary to maintain a log identifying the defective sections of the storage medium and further, to provide a replacement section.
An optical disk is an example of a storage medium having a very high storage density, and hence, requiring efficient defect management. A spiral track is formed on the surface of the disk from the center to the outer edge. The spiral track forms many separately identifiable tracks, and each track is further divided into a plurality of sectors. Alternatively, the tracks can be formed on the surface of the disk as a plurality of concentric circles. A predetermined number of sectors are identified as a group, there being one to many groups on the disk. The optical disk may have many defective sectors due to particles, contaminants, or other surface defects. A number of spare sectors are set aside on the disk, for example, a portion of the spare sectors are located at the end of each group, as replacements for defective sectors. Many defective sectors can be found by performing a surface analysis of the disk. During surface analysis, known data is written to a sector and read back under stress conditions. Surface analysis, if performed, may be accomplished by the disk manufacturer, or may be completed during the formatting process.
Defective sectors found during surface analysis, referred to as primary defects, are taken out of service, and a logical block address (LBA) of the defective sector is reassigned to the next physical sector. Thus, there are unused sectors on the disk, and the remaining sectors slip, that is, spare sectors reserved at the end of the disk will be used. These defective sectors are further recorded on the disk in a primary defect list (PDL). Other defective sectors may be found during the life of the disk, referred to as secondary defects, and will have their logical block addresses reassigned to a sector that exists in an area of the disk reserved for replacing secondary defects. According to an American National Standards Institute (ANSI), spares may be placed in spare areas of the disk without having LBAs associated therewith. After reassigning the LBA, the data is moved to the spare sector. All defects found during the life of the disk are recorded on the disk in a secondary defect list (SDL).
A standard, ISO/IEC 10089:1991 (E) 130 mm Rewritable Optical Cartridge for Information Interchange, hereinafter referred to as the standard, has been established for 130 mm optical disk cartridges and is hereby incorporated by reference. The standard describes a method for recording defective sectors in the PDL and SDL. The standard also describes how to document the format of the media which is maintained in a disk definition structure (DDS). The DDS, for example, defines the number of groups (g), the number of sectors per group (m) set aside for data, and the number of spares per group (n). According to the standard, a user zone is made up of N+1 tracks (track 0 to N, wherein tracks 0, 1, 2, N-2, N-1 and N are reserved for use by the defect management areas (DMA). Therefore, N-5 tracks are available to a user. A maximum of 2048 sectors may be allocated as spares for the primary and secondary defect lists.
The user zone is divided into g groups, wherein g must be greater than or equal to one and less than or equal to 2048. The number of sectors per track (SPT) varies depending upon whether 1024 byte sectors or 512 byte sectors are defined. In the case of 1024 byte sectors, there will exist 17 SPT, and for 512 byte sectors, there will be 31 SPT. When initializing a disk for 1024-byte sectors, and each group, g, contains m sectors for data and n sectors as spares, equation [1] must be satisfied: EQU g*(m+n).ltoreq.[17*(N-5)]-2048. [1]
Similarly, when the disk is initialized using 512-byte sectors, equation [2] must be satisfied: EQU g*(m+n).ltoreq.[31*(N-5)]-2048. [2]
In a host computer system, the data sectors m are used for data storage and are viewed as a contiguous memory element of logical blocks, wherein each logical block is addressed by its LBA. Each data sector, then, is individually addressable and may be written to or read from individually.
The method to be used for replacing defective sectors with spare sectors is not set forth by the standard. The method for replacing defective sectors basically requires that the logical block address of the defective sector be reassigned by a spare sector. Because the order of information may be rearranged on the disk, it is also necessary to locate an LBA when consecutive LBAs are not recorded on physically consecutive sectors. The data stored in the PDL, SDL, and DDS on the disk provide the basic information necessary to manage defective sectors. Although this information is on the disk, it does not lend itself to providing quick defect management.
One method of determining replacement sectors on a disk includes building a defect map for tracking all known defects. Such a defect map is built each time a disk is inserted into a drive (or when a drive is initialized with a disk therein). Building a defect map requires copying the PDL, SDL, and DDS from the disk to a memory. The defect map also requires entries identifying the beginning of each continuous section on the disk, and information about each discontinuity. A binary search of the defect map is performed when establishing a track and sector number for a LBA.
Defect maps can be large, and the time required to generate a defect map can be prohibitive, especially as the density of data capable of being stored on a disk increases. The standard allows for up to 2048 defective sectors in the PDL and the SDL. Four bytes of memory are required to describe each sector. Hence the PDL may require up to 8 K bytes of memory. The SDL lists both defective sectors and replacement sectors, and hence may require as many as 16 K bytes of memory. Having a potentially large PDL and/or SDL means that substantial time is required to search these lists.
Thus what is needed is a method for more quickly locating spare sectors for replacing secondary defects that does not require large amounts of memory and substantial processing times for generating potentially large tables.